Laboratório 7: Filas de Prioridade e Heap Binário

O que Estamos Construindo 🎯

  • A Estrutura de Dados: Um Fila de Prioridade (FP).
    • É um tipo abstrato de dados, como uma lista ou fila, mas com uma particularidade.
    • Cada item tem uma "prioridade" (uma chave).
    • Quando você faz "pop", você semprerecebe o item com a maior prioridade.
  • As Operações:
    • 1. push(k)
    • 2. peek()
    • 3. pop()
  • A Implementação: Vamos usar um Heap Binário Máximo.
  • Por que um Heap? É eficiente! Um heap nos oferece:
    • push: O(log N)
    • pop: O(log N)
    • peek: O(1)

O que é um Heap Máximo?

Uma árvore binária com duas regras simples:

1. Propriedade de Forma

É uma árvore binária completa. Todos os níveis estão cheios, exceto possivelmente o último, que é preenchido da esquerda para a direita. Não há lacunas.

Clique em uma folha para remover

2. Propriedade de Heap Máximo

A chave de um pai é maior ou igual a as chaves dos filhos. Isso garante que o maior elemento esteja sempre na raiz.

Armazenando a Árvore 💾

Como a árvore é completa, podemos armazená-la perfeitamente em um array simples.

Matemática de Índices (base 0)

Para um nó no índice i:

  • Pai(i - 1) // 2
  • Filho Esquerdo2 * i + 1
  • Filho Direito2 * i + 2

Dica:Memorize essas fórmulas! Elas são a chave para navegar pela "árvore" dentro do seu array.